#include <cstdio>
#include <cstring>

int min( int a, int b ) { return ( a < b )?a :b; }

short f[ 501 ][ 501 ][ 53 ];
char a[ 501 ], b[ 501 ];
int n, m;

inline int gn( char c )
{
    if ( c >= 'a' && c <= 'z' ) return c - 'a' + 1;
    return c - 'A' + 27;
}

void init( )
{
    int i, j, k;
    n = strlen( a );
    m = strlen( b );
    for ( i = 0; i <= m; i++ )
        for ( j = 0; j <= n; j++ )
            for ( k = 0; k <= 52; k++ )
                f[ i ][ j ][ k ] = 10000;
    f[ 0 ][ 0 ][ 0 ] = 0;
    for ( i = 1; i <= n; i++ )
        f[ 0 ][ i ][ 0 ] = i;
}

void work( )
{
    int i, j, k, l, ans = 100000000;
    for ( i = 1; i <= m; i++ )
    {
        f[ i ][ 0 ][ 0 ] = f[ i - 1 ][ 0 ][ 0 ] + 1;
        for ( j = 1; j <= n; j++ )
        {
            f[ i ][ j ][ 0 ] = min( f[ i ][ j ][ 0 ], f[ i ][ j - 1 ][ 0 ] + 1 );
            f[ i ][ j ][ 0 ] = min( f[ i ][ j ][ 0 ], f[ i - 1 ][ j ][ 0 ] + 1 );
            f[ i ][ j ][ 0 ] = min( f[ i ][ j ][ 0 ], f[ i - 1 ][ j - 1 ][ 0 ] + 1 );
            if ( b[ i - 1 ] == a[ j - 1 ] )
                f[ i ][ j ][ 0 ] = min( f[ i ][ j ][ 0 ], f[ i - 1 ][ j - 1 ][ 0 ] );
            for ( k = 1; k <= 52; k++ )
            {
                f[ i ][ j ][ k ] = min( f[ i ][ j ][ k ], f[ i - 1 ][ j - 1 ][ k ] + 1 );
                f[ i ][ j ][ k ] = min( f[ i ][ j ][ k ], f[ i ][ j - 1 ][ k ] + 1 );
                f[ i ][ j ][ k ] = min( f[ i ][ j ][ k ], f[ i - 1 ][ j ][ k ] + 1 );
                if ( gn( b[ i - 1 ] ) == k )
                {
                    f[ i ][ j ][ k ] = min( f[ i ][ j ][ k ], f[ i - 1 ][ j - 1 ][ k ] );
                    for ( l = 0; l <= 52; l++ )
                    {
                        if ( l == k ) continue;
                        f[ i ][ j ][ k ] = min( f[ i ][ j ][ k ], f[ i - 1 ][ j - 1 ][ l ] + 1 );
                    }
                }
            }
        }
    }
    for ( i = 0; i <= 52; i++ )
        if ( ans > f[ m ][ n ][ i ] )
            ans = f[ m ][ n ][ i ];
    printf("%d\n", ans);
}

int main( )
{
    while ( scanf("%s", a) && a[ 0 ] != '#' )
    {
        scanf("%s", b);
        init( );
        work( );
    }
    return 0;
}
